In this paper we propose to study generalization of neural networks on small algorithmically
generated datasets. In this setting, questions about data efficiency,
memorization, generalization, and speed of learning can be studied in great detail.
In some situations we show that neural networks learn through a process
of “grokking" a pattern in the data, improving generalization performance from
random chance level to perfect generalization, and that this improvement in generalization
can happen well past the point of overfitting. We also study generalization as
a function of dataset size and find that smaller datasets require increasing amounts
of optimization for generalization. We argue that these datasets provide a fertile
ground for studying a poorly understood aspect of deep learning: generalization
of overparametrized neural networks beyond memorization of the finite training
dataset.
本稿では、アルゴリズムによって生成された小規模データセットにおけるニューラルネットワークの汎化について研究することを提案する。この設定では、データ効率、記憶、汎化、学習速度といった問題を詳細に研究することができる。
状況によっては、ニューラルネットワークがデータ内のパターンを「grokkingする」(理解する)プロセスを通じて学習し、汎化性能をランダムな偶然レベルから完全な汎化レベルまで向上させること、そしてこの汎化の向上は過学習の域をはるかに超えて起こり得ることを示す。また、データセットサイズの関数としての汎化についても研究し、データセットが小さいほど、汎化のための最適化の必要量が増えることを明らかにした。これらのデータセットは、深層学習のあまり理解されていない側面、すなわち有限の訓練データセットの記憶を超えた、過剰パラメータ化されたニューラルネットワークの汎化を研究するための肥沃な土壌を提供すると主張する。
The generalization of overparameterized neural networks has long been a source of interest to the
machine learning community since it defies intuitions derived from classical learning theory. In
this paper we show that training networks on small algorithmically generated datasets can reliably
exhibit unusual generalization patterns, clearly decoupled from performance on the training set, in a
significantly more pronounced way than such effects manifest on datasets derived from natural data
(see Figure 1, left, for an example). Such experiments can be quickly reproduced on a single GPU,
and this makes them convenient testbeds for theories of generalization.
過剰パラメータ化されたニューラルネットワークの汎化は、古典的な学習理論から導かれる直感に反するため、機械学習コミュニティの長年の関心事であった。本稿では、アルゴリズムによって生成された小規模なデータセットを用いた学習ネットワークが、学習セットのパフォーマンスとは明確に切り離された、特異な汎化パターンを、自然データから得られたデータセットで現れるよりもはるかに顕著に示すことを示す（例として図1の左を参照）。このような実験は単一のGPUで迅速に再現できるため、汎化理論の便利なテストベッドとなる。
Figure 1: Left. Grokking: A dramatic example of generalization far after overfitting on an algorithmic
dataset. We train on the binary operation of division mod 97 with 50%
of the data in the training set.
Each of the 97 residues is presented to the network as a separate symbol, similar to the representation
in the figure to the right. The red curves show training accuracy and the green ones show validation
accuracy. Training accuracy becomes close to perfect at < \(10^3\) optimization steps, but it takes
close to \(10^6\) steps for validation accuracy to reach that level, and we see very little evidence of any generalization until \(10^5\)
steps. Center. Training time required to reach 99% validation accuracy
increases rapidly as the training data fraction decreases. Right. An example of a small binary
operation table. We invite the reader to make their guesses as to which elements are missing.
図1：左。グロッキング：アルゴリズムデータセットにおける過学習後、はるかに汎化が進んだ劇的な例。学習セットのデータの50%を用いて、97を法とする除算の二項演算を学習します。97個の残基はそれぞれ、右図の表現と同様に、ネットワークに個別のシンボルとして提示されます。赤い曲線は学習精度、緑の曲線は検証精度を示します。学習精度は最適化ステップ数が\(10^3\)未満でほぼ完璧になりますが、検証精度がそのレベルに達するには\(10^6\)ステップ近くかかり、\(10^5\)ステップまで汎化の兆候はほとんど見られません。中央。学習データの割合が減少するにつれて、99%の検証精度に達するために必要な学習時間は急速に増加します。右。小さな二項演算テーブルの例。どの要素が欠けているかは、読者の推測にお任せします。
The datasets we consider are binary operation tables of the form \(a◦b=c\) where \(a,b,c\) are discrete symbols with no internal structure, and ◦
is a binary operation. Examples of binary operations include
addition, composition of permutations, and bivariate polynomials. Training a neural network on a
proper subset of all possible equations then amounts to filling in the blanks of the binary op table,
much like solving a Sudoku puzzle. An example is shown on the right in Figure 1. Since we use
distinct abstract symbols for all distinct elements \(a,b,c\) involved in the equations, the network is not
made aware of any internal structure of the elements, and has to learn about their properties only
from their interactions with other elements. For example the network doesn't see numbers in decimal
notation, or permutations in line notation.
本稿で検討するデータセットは、\(a◦b=c\) という形式の二項演算テーブルであり、\(a,b,c\) は内部構造を持たない離散シンボルであり、◦ は二項演算である。二項演算の例には、加算、順列の合成、二変数多項式などがある。ニューラルネットワークをすべての可能な方程式の適切なサブセットで学習させることは、数独パズルを解くのと同じように、2値演算テーブルの空白を埋めることに相当します。図1の右側に例を示します。方程式に含まれるすべての異なる要素 (a, b, c) に異なる抽象記号を使用しているため、ネットワークは要素の内部構造を認識せず、他の要素との相互作用からのみ要素の特性を学習する必要があります。例えば、ネットワークは10進表記の数値や、直線表記の順列を認識しません。
Our contributions are as follows:
私たちの貢献は以下の通りです。
All of our experiments used a small transformer trained on datasets of equations of the form \(a◦b=c\), where each of “\(a\)", “\(◦\)", “\(b\)", “\(=\)", and “\(c\)" is a separate token. Details of the operations studied, the architecture, training hyperparameters and tokenization can be found in Appendix A.1.
すべての実験では、\(a◦b=c\) 形式の方程式のデータセットで学習された小規模な変換器を使用しました。ここで、「\(a\)」、「\(◦\)」、「\(b\)」、「\(=\)」、「\(c\)」はそれぞれ独立したトークンです。検討した演算、アーキテクチャ、学習ハイパーパラメータ、トークン化の詳細については、付録 A.1 を参照してください。
Deep learning practitioners are used to seeing small improvements in validation accuracy after
validation loss stops decreasing. A double descent of validation loss has been documented in
some circumstances, but is considered unusual among practitioners Nakkiran et al. (2019); Belkin
et al. (2018); d'Ascoli et al. (2020). On the small algorithmic datasets that we study, improved
generalization after initial overfitting occurs for a range of models, optimizers, and dataset sizes,
and in some cases these effects are extremely pronounced. A typical example is shown for modular
division in Figure 1. There we see that validation accuracy starts increasing beyond chance level
only after 1000 times more optimization steps than are required for training accuracy to get close to
optimal. In Figure 4 the training/validation losses are also plotted and we see the double descent of
the validation loss.
ディープラーニングの実践者は、検証損失の減少が止まった後に検証精度がわずかに向上するのを見ることに慣れています。検証損失の二重降下は、いくつかの状況で文書化されていますが、実践者の間では珍しいと考えられています（Nakkiran et al. (2019); Belkin et al. (2018); d'Ascoli et al. (2020)）。私たちが研究している小規模なアルゴリズムデータセットでは、初期の過学習後に汎化が改善され、さまざまなモデル、最適化装置、データセットサイズで発生し、場合によってはこれらの効果が非常に顕著です。図1のモジュラー除算の典型的な例を示します。ここでは、訓練精度が最適に近づくために必要な最適化ステップの1000倍を経た後にのみ、検証精度が偶然のレベルを超えて増加し始めることがわかります。図4には、訓練/検証損失もプロットされており、検証損失の二重降下が見られます。
We found these behaviors to be typical for all the binary operations for dataset sizes that were close
to the minimal dataset size for which the network generalized within the allotted optimization budget.
For larger dataset sizes, the training and validation curves tend to track each other more closely.
これらの挙動は、割り当てられた最適化予算内でネットワークが汎化できる最小データセットサイズに近いデータセットサイズの場合、すべての二項演算において典型的であることがわかりました。データセットサイズが大きいほど、トレーニング曲線と検証曲線は互いにより密接に一致する傾向があります。
In a typical supervised learning problem, decreasing the amount of training data decreases the converged generalization performance of the model when the optimization procedure is capable of interpolating the training data. In our setting, we observe a different phenomenon: while the converged performance stays constant at 100% within a range of training dataset sizes, the optimization time required to achieve that performance grows quicky as the dataset size is decreased.
典型的な教師あり学習問題では、最適化手順が学習データを補間できる場合、学習データの量を減らすとモデルの収束汎化性能が低下します。しかし、私たちの設定では異なる現象が観察されます。学習データセットのサイズの範囲内では収束性能は100%で一定ですが、データセットのサイズが小さくなるにつれて、その性能を達成するために必要な最適化時間は急速に増加します。
Figure 1 (center) shows median number of optimization steps until validation performance first reaches 99% for the product in abstract group S5. In the vicinity of 25-30% of data, a decrease of 1% of training data leads to an increase of 40-50% in median time to generalization. While the number of steps until validation accuracy > 99% grows quickly as dataset size decreases, the number of steps until the train accuracy first reaches 99% generally trends down as dataset size decreases and stays in the range of 103-104 optimization steps. We've observed a similar pattern of exponential increase in optimization time until reaching generalization as dataset size decreases on all the algorithmic tasks for which we could get the networks to generalize.
図 1 (中央) は、抽象グループ S5 の製品について、検証性能が初めて 99% に達するまでの最適化ステップ数の中央値を示しています。データの 25～30% 付近では、トレーニングデータが 1% 減少すると、汎化までの時間の中央値が 40～50% 増加します。データセットのサイズが小さくなると、検証精度が 99% を超えるまでのステップ数は急速に増加しますが、トレーニング精度が初めて 99% に達するまでのステップ数は、データセットのサイズが小さくなると一般的に減少する傾向があり、103～104 の最適化ステップの範囲にとどまります。ネットワークを汎化できるすべてのアルゴリズムタスクにおいて、データセットのサイズが小さくなると、汎化に達するまでの最適化時間が指数関数的に増加するという同様のパターンが見られました。
We've measured the mean accuracy across three runs for training datasets consisting of different
fractions of all available equations for a variety of binary operations listed in Appendix A.1.1. The
results are presented in Figure 2 (right).
付録A.1.1に記載されている様々な二項演算について、利用可能なすべての方程式の異なる割合で構成されるトレーニングデータセットに対して、3回の実行で平均精度を測定しました。結果は図2（右）に示されています。
Figure 2: Left. Different optimization algorithms lead to different amounts of generalization within an optimization budget of \(10^5\) steps for the problem of learning the product in the abstract group \(S_5\). Weight decay improves generalization the most, but some generalization happens even with full batch optimizers and models without weight or activation noise at high percentages of training data. Suboptimal choice hyperparameters severely limit generalization. Not shown: training accuracy reaches 100% after \(10^3-10^4\) updates for all optimization methods. Right. Best validation accuracy achieved after \(10^5\) steps on a variety of algorithmic datasets, averaged over 3 seeds. Generalization happens at higher percentages of data for intuitively more complicated and less symmetrical operations.
図2: 左。抽象群 \(S_5\) の積を学習する問題において、最適化アルゴリズムによって、最適化予算 \(10^5\) ステップ内での汎化の程度が異なります。重み減衰は汎化を最も向上させますが、フルバッチ最適化器や重みや活性化ノイズのないモデルでも、トレーニングデータの割合が高いと汎化が起こります。最適でないハイパーパラメータの選択は、汎化を著しく制限します。図示されていませんが、すべての最適化手法において、トレーニング精度は \(10^3-10^4\) 回の更新後に 100% に達します。右。さまざまなアルゴリズムデータセットで \(10^5\) ステップ後に達成された最高の検証精度は、3 つのシードで平均化されています。直感的に複雑で対称性が低い操作の場合、データの割合が高いほど汎化が起こります。
Since the operands are presented to the neural network as unrelated abstract symbols, the operations \(x+y\;(mod\;p-1)\) and \(x*y\;(mod\; p)\) with a prime number \(p\) and non-zero \(x,y\) are indistinguishable from the neural network's perspective (and similarly \(x−y\;(mod\;p−1)\) and \(x/y\;(mod\;p)\)). This
is because every nonzero residue modulo a prime can be represented as a power of a primitive root. This representation shows the equivalence (up to renaming of symbols) of modular addition modulo
\(p−1\) and modular multiplication modulo p. We see in Figure 2 (right) that \(x−y\) and \(x/y\) indeed take about the same amount of data for generalization to occur.
ニューラルネットワークにはオペランドが無関係な抽象シンボルとして提示されるため、素数 \(p\) と非ゼロ \(x,y\) を用いた演算 \(x+y\;(mod\;p-1)\) と \(x*y\;(mod\; p)\) は、ニューラルネットワークの観点からは区別がつきません（同様に \(x−y\;(mod\;p−1)\) と \(x/y\;(mod\;p)\) も同様です）。これは、素数を法とするすべての非ゼロ剰余が、原始根のべき乗として表現できるためです。この表現は、\(p−1\) を法とするモジュラー加算と p を法とするモジュラー乗算が（シンボルの名前変更を除けば）等価であることを示しています。図2（右）を見ると、\(x−y\)と\(x/y\)は、一般化が起こるために実際にはほぼ同じ量のデータを必要とすることがわかります。
Some of the operations listed in Figure 2 (right) are symmetric with respect to the order of the operands (\(x+y, x∗y, x^2+y^2\) and \(x^2
+xy+y^2\)). Such operations tend to require less data for generalization than closely related non-symmetrical counterparts (\(x−y, x/y, x^2+xy+y^2+x\)). We believe this effect might be partially architecture-dependent, since it's easy for a transformer to learn a symmetric function of the operands by ignoring positional embedding.
図2（右）に挙げた演算の中には、オペランドの順序に関して対称的なものがあります（\(x+y, x∗y, x^2+y^2\) および \(x^2
+xy+y^2\)）。このような演算は、密接に関連する非対称な演算（\(x−y, x/y, x^2+xy+y^2+x\)）よりも、一般化に必要なデータ量が少なくなる傾向があります。この効果は、位置埋め込みを無視することで、トランスフォーマーがオペランドの対称関数を学習することが容易なため、部分的にアーキテクチャに依存する可能性があると考えています。
Some operations (for example \(x^3+xy^2+y\;(mod\;97)\)) didn't lead to generalization within the allowed optimization budget at any percentage of data up to 95%. The converged models effectively just memorized the training dataset without finding any real patterns in the data. To such a model, the data is effectively random.
一部の演算（例えば\(x^3+xy^2+y\;(mod\;97)\)）は、95%までのデータの割合において、許容される最適化予算内での汎化に至りませんでした。収束したモデルは、データに真のパターンを見出すことなく、実質的にはトレーニングデータセットを記憶しただけだったのです。このようなモデルにとって、データは事実上ランダムです。
The operation \([x/y\;(mod\;p)\) if \(y\) is odd, otherwise \(x−y\;
(mod\;p)]\) requires the network to learn a mix of several simple operations -in particular the role of \(x\) has to be interpreted as a residue in the additive group when it's paired with an even y, and as a residue in the multiplicative group when it's paired with an odd \(y\). This shows that generalization can happen even for operations that are not cleanly interpretable via group or ring operations.
\(y\)が奇数の場合は\([x/y\;(mod\;p)\)、そうでない場合は\(x−y\;
(mod\;p)]\)という演算は、ネットワークが複数の単純な演算を組み合わせて学習することを要求します。特に、\(x\)の役割は、偶数yと組み合わせる場合は加法群の剰余として、奇数yと組み合わせる場合は乗法群の剰余として解釈する必要があります。これは、群演算や環演算では明確に解釈できない演算であっても、一般化が可能であることを示しています。
We've tried various forms of regularization to see what can induce networks to generalize better on our datasets. Here we present the data efficiency curves on a particular dataset S5 for a variety of
interventions: full-batch gradient descent, stochastic gradient descent, large or small learning rates, residual dropout Srivastava et al. (2014), weight decay Loshchilov & Hutter (2017) and gradient
noise Neelakantan et al. (2015). The results are shown in Figure 2 (left).
我々は、様々な形態の正則化を試し、ネットワークがデータセット上でより良く汎化するために何が効果的かを探りました。ここでは、特定のデータセットS5において、様々な介入（フルバッチ勾配降下法、確率的勾配降下法、学習率の大小、残差ドロップアウト（Srivastava et al. 2014）、重み減衰（Loshchilov & Hutter 2017）、勾配ノイズ（Neelakantan et al. 2015））を行った場合のデータ効率曲線を示します。結果は図2（左）に示されています。
We find that adding weight decay has a very large effect on data efficiency, more than halving the amount of samples needed compared to most other interventions. We found that weight decay towards the initialization of the network is also effective, but not quite as effective as weight decay towards the origin. This makes us believe that the prior, that approximately zero weights are suitable for small algorithmic tasks, explains part, but not all of the superior performance of weight decay. Adding some noise to the optimization process (e.g. gradient noise from using minibatches, Gaussian noise applied to weights before or after computing the gradients) is beneficial for generalization, consistent with the idea that such noise might induce the optimization to find flatter minima that generalize better. We found that learning rate had to be tuned in a relatively narrow window for the generalization to happen (within 1 order of magnitude).
重み減衰を追加すると、データ効率に非常に大きな効果があり、他のほとんどの介入と比較して必要なサンプルの量が半分以上削減されることがわかりました。ネットワークの初期化に向かう重み減衰も効果的ですが、原点に向かう重み減衰ほど効果的ではないことがわかりました。このことから、ほぼゼロの重みが小規模なアルゴリズムタスクに適しているという事前条件は、重み減衰の優れたパフォーマンスの一部を説明しますが、すべてを説明するわけではないと考えられます。最適化プロセスにノイズを追加すると（ミニバッチの使用による勾配ノイズ、勾配を計算する前または後に重みに適用されるガウスノイズなど）、一般化に役立ち、このようなノイズによって最適化がより一般化しやすい平坦な最小値を見つける可能性があるという考えと一致しています。一般化が発生するには、学習率を比較的狭いウィンドウ（1 桁以内）で調整する必要があることがわかりました。
In order to gain some insight into networks that generalize, we visualized the matrix of the output layer for the case of modular addition and S5. In Figure 3 we show t-SNE plots of the row vectors. For some networks we find clear reflections of the structure of the underlying mathematical objects in the plots. For example the circular topology of modular addition is shown with a ‘number line' formed by adding 8 to each element. The structure is more apparent in networks that were optimized with weight decay.
汎化ネットワークへの洞察を深めるため、モジュラー加算とS5の場合の出力層の行列を視覚化しました。図3は、行ベクトルのt-SNEプロットを示しています。一部のネットワークでは、プロットに基礎となる数学的オブジェクトの構造が明確に反映されています。例えば、モジュラー加算の円形トポロジーは、各要素に8を加算することで形成される「数直線」で示されています。この構造は、重み減衰を用いて最適化されたネットワークではより明確です。
We have seen that in the datasets we studied, small algorithmic binary operation tables, effects such as double descent or late generalization, and improvements to generalization from interventions like weight decay can be striking. This suggests that these datasets could be a good place to investigate aspects of generalization. For example, we plan to test whether various proposed measures of minima flatness correlate with generalization in our setting.
私たちが研究したデータセットでは、小規模なアルゴリズム的二項演算テーブル、二重降下法や後期汎化といった効果、そして重み減衰のような介入による汎化の改善が顕著に現れることが確認されました。これは、これらのデータセットが汎化のさまざまな側面を調査するのに適した場所となる可能性を示唆しています。例えば、私たちの設定において、最小平坦性に関する様々な提案された指標が汎化と相関するかどうかを検証する予定です。
We have also seen that visualizing the embedding spaces of these neural networks can show natural kinds of structure, for example in problems of modular arithmetic the topology of the embeddings tends to be circles or cylinders. We also see that the network tends to idiosyncratically organize the embeddings by various residues. Whilst the properties of these mathematical objects are familiar to us, we speculate that such visualizations could one day be a useful way to gain intuitions about novel mathematical objects.
また、これらのニューラルネットワークの埋め込み空間を視覚化することで、自然な構造を表現できることも確認しました。例えば、モジュラー算術の問題では、埋め込みの位相は円や円筒形になる傾向があります。また、ネットワークは様々な留数によって埋め込みを特異な形で構成する傾向があることもわかりました。これらの数学的対象の性質は私たちにとって馴染み深いものですが、このような視覚化は将来、新しい数学的対象についての直感を得るための有用な手段となる可能性があると考えています。
Figure 3: Left. t-SNE projection of the output layer weights from a network trained on S5. We see clusters of permutations, and each cluster is a coset of the subgroup \(\langle(0,3)(1,4),(1,2)(3,4)\rangle\) or one of its conjugates. Right. t-SNE projection of the output layer weights from a network trained on modular addition. The lines show the result of adding 8 to each element. The colors show the residue of each element modulo 8.
図3: 左: S5で学習したネットワークの出力層の重みのt-SNE投影。順列のクラスターが見られ、各クラスターは部分群\(\langle(0,3)(1,4),(1,2)(3,4)\rangle\)またはその共役群の1つである。右: モジュラー加算で学習したネットワークの出力層の重みのt-SNE投影。線は各要素に8を加算した結果を示している。色は各要素を8で割った剰余を示している。
In addition, we document an interesting phenomenon, where the number of optimization steps needed to reach a given level of performance increases quickly as we reduce the size of the training dataset. Since this represents a way trade compute for performance on smaller amounts of data, it would be useful to investigate in future work whether the effect is also present for other datasets.
さらに、学習データセットのサイズが小さくなると、所定の性能レベルに到達するために必要な最適化ステップ数が急激に増加するという興味深い現象を明らかにしました。これは、より少ないデータ量における性能と計算コストをトレードオフする方法を示しているため、今後の研究では、この効果が他のデータセットにも存在するかどうかを調査することが有用です。
The following are the binary operations that we have tried (for a prime number p =97):
以下は、私たちが試した二項演算です（素数 p =97 の場合）。
\[
\begin{align}
&x◦y=x+y\;(mod\;p)\;for\; 0≤x,y\lt p \\
&x◦y=x−y\;(mod\:p)\:for\; 0≤x,y\lt p \\
&x◦y=x/y\;(mod\;p)\;for\; 0≤x\lt p,\; 0\lt y\lt p\\
&x◦y=[x/y\;(mod\;p)\;if\; y\;is\; odd,\; otherwise\; x−y\;(mod\;p)]\; for\; 0≤x,y\lt p\\
&x◦y=x^2+y^2\;(mod\;p)\;for\; 0≤x,y\lt p\\
&x◦y=x^2+xy+y^2\;(mod\;p)\;for\; 0≤x,y\lt p\\
&x◦y=x^2+xy+y^2+x\:(mod\:p)\;for\; 0 ≤x,y\lt p\\
&x◦y=x^3+xy\;(mod\;p)\;for\; 0≤x,y\lt p\\
&x◦y=x^3+xy^2+y\;(mod\;p)\;for\; 0≤x,y\lt p\\
&x◦y=x·y\;for\; x,y∈S_5 \\
&x◦y=x·y·x^{-1}\;for\; x,y∈S_5\\
&x◦y=x·y·x\;for\; x,y∈S_5
\end{align}
\]
For each binary operation we constructed a dataset of equations of the form \(\langle x \rangle \langle op \rangle \langle y \rangle \langle = \rangle \langle x◦y \rangle\), where \(\langle a \rangle\)
stands for the token corresponding to element \(a\).
それぞれの二項演算について、\(\langle x \rangle \langle op \rangle \langle y \rangle \langle = \rangle \langle x◦y \rangle\) という形式の方程式のデータセットを構築しました。ここで、\(\langle a \rangle\) は要素 \(a\) に対応するトークンを表します。
For each training run, we chose a fraction of all available quations at random and declared them to be the training set, with the rest of equations being the validation set.
各トレーニング実行ごとに、利用可能なすべての方程式の一部をランダムに選択してトレーニング セットとして宣言し、残りの方程式を検証セットとしました。
We trained a standard decoder-only transformer Vaswani et al. (2017) with causal attention masking, and calculated loss and accuracy only on the answer part of the equation. For all experiments we used a transformer with 2 layers, width 128, and 4 attention heads, with a total of about \(4·10^5\) non-embedding parameters.
Vaswani et al. (2017) の標準的なデコーダーのみの変換器を因果的注意マスキングを用いて学習し、方程式の解答部分のみの損失と精度を計算しました。全ての実験において、2層、幅128、4つの注意ヘッド、合計約\(4·10^5\)個の非埋め込みパラメータを持つ変換器を使用しました。
We have tuned optimization hyperparameters by running experiments on modular addition and product in \(S_5\). For final configuration of hyperparameters we have chosen a balance of performance we saw on \(S_5\) and simplicity (for example we chose not to anneal the learning rate for the experiments in the paper even though it performed better in some situations). For most experiments we used AdamW optimizer with learning rate \(10^{-3}\), weight decay 1, \(β_1=0:9, β_2=0:98\), linear learning rate warmup over the first 10 updates, minibatch size 512 or half of training dataset size (whichever was smaller) and optimization budget of \(10^5\) gradient updates.
\(S_5\) でモジュラー加算と積の実験を実行することで、最適化ハイパーパラメータを調整しました。最終的なハイパーパラメータの設定では、\(S_5\) で確認したパフォーマンスとシンプルさのバランスを選択しました（例えば、論文の実験では学習率のアニールを行わない選択をしましたが、状況によってはより良いパフォーマンスが得られました）。ほとんどの実験では、学習率 \(10^{-3}\)、重み減衰 1、\(β_1=0:9, β_2=0:98\)、最初の10回の更新で線形学習率ウォームアップ、ミニバッチサイズ 512 またはトレーニングデータセットサイズの半分（いずれか小さい方）、最適化予算 \(10^5\) の勾配更新で AdamW オプティマイザーを使用しました。
In section 3.3 we have also tried the following variants (listed in the reading order for Figure 2 left):
セクション 3.3 では、次のバリエーションも試しました (図 2 の左の読み取り順にリストされています)。
For experiments reported in Section 3.1.1 we increased the optimization budget to \(5･10^5\) optimization steps in order to capture the increase of time to perfect generalization better.
セクション3.1.1で報告された実験では、完全な一般化までの時間の増加をより適切に捉えるために、最適化予算を \(5･10^5\) 最適化ステップに増やしました。
For the experiments reported in Section 3.1 we increased the optimization budget to \(10^6\), and used Adam optimizer with no weight decay, for emphasizing how late into the optimization process the generalization can begin.
セクション 3.1 で報告した実験では、最適化プロセスのどの段階で一般化を開始できるかを強調するために、最適化予算を \(10^6\) に増やし、重み減衰のない Adam オプティマイザーを使用しました。
We've repeated each experiment for each dataset size with 3 random seeds, with the exception of
experiments in section 3.1.1, where we've aggregated results over 7 random seeds.
各データセットサイズに対して、3つのランダムシードを使用して各実験を繰り返しました。ただし、セクション3.1.1の実験では、7つのランダムシードで結果を集計しました。
In Figure 4 we show the loss curves that correspond to the accuracy curves in Figure 1.
図 4 に、図 1 の精度曲線に対応する損失曲線を示します。
Figure 4: The loss curves for modular division, train and validation. We see the validation loss increases from \(10^2\) to about \(10^5\) optimization steps before it begins a second descent.
図4: モジュラー分割、学習、検証の損失曲線。検証損失は、最適化ステップ数 \(10^2\) から約 \(10^5\) まで増加し、その後2回目の降下が始まることがわかります。
In Figure 5 we show an example of a binary operation table that the network can actually solve.
図 5 に、ネットワークが実際に解決できるバイナリ演算テーブルの例を示します。
Figure 5: One of the binary operation tables presented to the networks that the network can perfectly fill in. Each symbol is represented as a letter in English, Hebrew, or Greek alphabet for reader's convenience. We invite the reader to guess which operation is represented here.
図5：ネットワークに提示された二項演算表の一つ。ネットワークはこれを完全に埋めることができる。各記号は、読者の便宜を図るため、英語、ヘブライ語、またはギリシャ語のアルファベットで表されている。読者は、ここでどの演算が表されているかを推測することができる。
In this paper we study training and generalization dynamics on small simple algorithmic datasets. In the past, algorithmic datasets have been used to probe the capability of neural networks to perform symbolic and algorithmic reasoning. For example the tasks of copying, reversing, and sorting randomly generated sequences, and performing arithmetic operations of multi-digit numbers, have been used as standard benchmarks for sequence-to-sequence models Graves et al. (2014), Weston et al. (2014) Kaiser & Sutskever (2015) Reed & De Freitas (2015), Grefenstette et al. (2015), Zaremba & Sutskever (2015), Graves (2016), Dehghani et al. (2018). Typically in these works however the emphasis is on the performance in the unlimited data regime, with generalization often studied with respect to input sequence length. Some papers study the sample complexity on algorithmic tasks Reed & De Freitas (2015), but mostly focus on the impact of architectural choices. In contrast we study the phenomenon of generalization in data-limited regime, with an emphasis on phenomena that we believe to be architecture-agnostic.
本稿では、小規模で単純なアルゴリズムデータセットにおける学習と汎化のダイナミクスについて考察する。これまで、アルゴリズムデータセットは、ニューラルネットワークの記号的推論およびアルゴリズム的推論を実行する能力を調査するために使用されてきた。例えば、ランダムに生成されたシーケンスのコピー、反転、ソート、および多桁の数値の算術演算といったタスクは、シーケンスツーシーケンスモデルの標準的なベンチマークとして使用されてきている（Graves et al. (2014), Weston et al. (2014) Kaiser & Sutskever (2015) Reed & De Freitas (2015), Grefenstette et al. (2015), Zaremba & Sutskever (2015), Graves (2016), Dehghani et al. (2018)）。しかしながら、これらの研究では通常、無制限データ領域におけるパフォーマンスに重点が置かれており、入力シーケンスの長さに対する汎化が研究されることが多い。いくつかの論文では、アルゴリズムタスクにおけるサンプル複雑度を研究していますが（Reed & De Freitas (2015)）、その多くはアーキテクチャの選択の影響に焦点を当てています。これに対し、我々はデータ制限領域における汎化現象を研究しており、特にアーキテクチャに依存しないと考えられる現象に重点を置いています。
Algorithmically generated reasoning datasets like bAbI Weston et al. (2015) encourage work on studying generalization in data-limited regime. Most results on such datasets however focus on a point estimate of performance of a particular architecture or training technique, whereas our main interest is in pointing out the change in generalization past the point where a particular architecture can memorize the training data completely.
bAbI Weston et al. (2015) のようなアルゴリズム生成推論データセットは、データ制限領域における汎化の研究を促進します。しかしながら、こうしたデータセットに関する結果のほとんどは、特定のアーキテクチャや学習手法の性能の点推定に焦点を当てています。一方、私たちの主な関心は、特定のアーキテクチャが学習データを完全に記憶できる時点以降の汎化の変化を指摘することにあります。
Neelakantan et al. (2015) has a “grok-like" learning curve on an algorithmic task, but it is related to optimization difficulty, whereas our phenomenon is specifically about generalization.
Neelakantan ら (2015) はアルゴリズムタスクに「grok のような」学習曲線を描いていますが、これは最適化の難しさと関連しています。一方、私たちの現象は特に一般化に関するものです。
In Saxton et al. (2019) they study generalization on procedurally generated math problems such as arithmetic and differentiation, but for the most part these tasks are more involved than the simple binary op problems we have studied and as such do not lend themselves to observing the kinds of phenomena we describe in this paper, since they would require an extremely large number of samples to master.
Saxton ら (2019) は、算術や微分などの手続き的に生成された数学の問題の一般化を研究していますが、これらのタスクの大部分は、私たちが研究してきた単純なバイナリ オペレーションの問題よりも複雑であり、そのため、習得するには非常に多数のサンプルが必要になるため、この論文で説明する種類の現象を観察するのには適していません。
In Jiang et al. (2019) they studied a large number of generalization or complexity measures on convolutional neural networks to see which, if any, are predictive of generalization performance. They find that flatness based measures that aim to quantify the sensitivity of the trained neural network to parameter perturbations are the most predictive. We conjectured that the grokking phenomena we report in this work may be due to the noise from SGD driving the optimization to flatter/simpler solutions that generalize better and hope to investigate in future work whether any of these measures are predictive of grokking.
Jiangら (2019) は、畳み込みニューラルネットワークにおける多数の汎化指標または複雑性指標を研究し、汎化性能を予測できる指標があるかどうかを調べました。その結果、訓練済みニューラルネットワークのパラメータ変動に対する感度を定量化することを目的とした平坦性に基づく指標が最も予測力が高いことがわかりました。本研究で報告したグロッキング現象は、SGDのノイズによって、より汎化性能の高い平坦/単純な解への最適化が促進された結果である可能性があると推測しており、今後の研究でこれらの指標のいずれかがグロッキングを予測できるかどうかを調査したいと考えています。
Zhang et al. (2016) finds that neural networks of sizes typically used in deep learning can interpolate arbitrary training data, and yet generalize when trained with semantically meaningful labels using appropriate optimization procedures. Our work shows a related phenomenon where neural networks can interpolate a small algorithmic training dataset without generalizing, but start generalizing when trained with SGD for longer.
Zhang et al. (2016) は、深層学習で一般的に用いられる規模のニューラルネットワークは、任意の学習データを補間できるものの、適切な最適化手順を用いて意味的に意味のあるラベルで学習させると、汎化能力を発揮することを発見しました。私たちの研究は、ニューラルネットワークが小規模なアルゴリズム学習データセットを補間する際には汎化能力を発揮しないものの、SGDを用いてより長い期間学習させると汎化能力を発揮し始めるという、関連する現象を示しています。
Nakkiran et al. (2019); Belkin et al. (2018) focus on the phenomenon of double descent in loss as a function of model and optimization procedure capacity. They find that the classical U-shaped validation loss curve is followed in some settings (including neural network training) by a second descent of loss that starts around the minimal capacity that is needed to interpolate any training data. We observe a second descent in validation loss (though not accuracy) as a function of the amount of training in some of our experiments, and it happens past the point of interpolating the training data. We believe that the phenomenon we describe might be distinct from the double descent phenomena described in Nakkiran et al. (2019); Belkin et al. (2018) because we observe the second descent in loss far past the first time the training loss becomes very small (tens of thousands of epochs in some of our experiments), and we don't observe a non-monotonic behavior of accuracy. The setting of small algorithmic datasets that we study also provides a smaller, more tractable playground for studying subtle generalization phenomena than natural datasets studied in Nakkiran et al. (2019).
Nakkiran et al. (2019); Belkin et al. (2018) は、モデルと最適化手順の容量の関数としての損失の二重降下現象に注目しています。彼らは、いくつかの設定（ニューラルネットワークの学習を含む）において、古典的なU字型の検証損失曲線に続いて、学習データを補間するために必要な最小容量付近から始まる損失の二次降下が起こることを発見しました。いくつかの実験では、学習量の関数として検証損失（精度は低下していないものの）の二次降下が観測され、これは学習データを補間する時点を過ぎた時点で発生します。私たちが説明する現象は、Nakkiran et al. (2019); Belkin et al. (2018) で説明されている二重降下現象とは異なる可能性があると考えています。なぜなら、損失の二次降下は、学習損失が非常に小さくなる最初の時点（いくつかの実験では数万エポック）をはるかに過ぎた時点を過ぎても観測され、精度の非単調な挙動は観測されないからです。私たちが研究する小規模なアルゴリズム データセットの設定は、Nakkiran ら (2019) で研究された自然なデータセットよりも、微妙な一般化現象を研究するための、より小規模で扱いやすい環境を提供します。
Figure 6: Effect on data efficiency of introducing \(k∈[0,10,100,1000,2000,
3000]\) outliers (examples
with random labels) into the training data. Small number of outliers doesn't noticeably impact
generalization performance, but a large number hinders it significantly.
図6: 訓練データに \(k∈[0,10,100,1000,2000,
3000]\) 個の外れ値（ランダムラベルの例）を導入した場合のデータ効率への影響。外れ値の数が少ない場合は汎化性能に目立った影響はありませんが、数が多い場合は汎化性能が大幅に低下します。
In this section we show data efficiency curves for a modified version of a binary op by introducing \(k\) outliers to the training dataset. More precisely, at the beginning of the experiment we randomly sample \(k\) equations from the training set and replace their answers with answers to other \(k\) equations randomly sampled from the training data. The rest of the equations in the training data and all the equations in the validation data are kept as before.
このセクションでは、訓練データセットに \(k\) 個の外れ値を導入することで、バイナリ演算の修正版のデータ効率曲線を示します。より正確には、実験開始時に訓練データセットから \(k\) 個の方程式をランダムにサンプリングし、その解を訓練データからランダムにサンプリングした他の \(k\) 個の方程式の解に置き換えます。訓練データの残りの方程式と検証データ内のすべての方程式は、以前のままです。
In this situation one could imagine one of the following scenarios unfolding. If the model class of neural networks optimized and regularized as before was not large enough to interpolate such “noisy" dataset, one could imagine the procedure converging to a solution that generalizes well, but denoises the training data (i.e. predicts \(c=a◦b\) as an answer even for the outlier equations \(a,b→c^\prime\) with \(c^\prime \neq c\)). On the other extreme it could be that the optimization procedure can find networks that interpolate the data, but the resulting models don't generalize, because they are forced to represent a considerably more complicated function than before (a simple function \(+k\) exceptions encoded in the training data).
このような状況では、以下のいずれかのシナリオが展開されると考えられます。前述のように最適化および正規化されたニューラルネットワークのモデルクラスが、このような「ノイズの多い」データセットを補間するのに十分な大きさでない場合、手順は、一般化は良好だがトレーニングデータのノイズを除去する（つまり、外れ値方程式 \(a,b→c^\prime\) かつ \(c^\prime \neq c\) に対しても \(c=a◦b\) を答えとして予測する）解に収束する可能性があります。もう一方の極端なケースでは、最適化手順によってデータを補間するネットワークが見つかるものの、結果として得られるモデルは一般化されません。これは、以前よりもかなり複雑な関数（トレーニングデータにエンコードされた単純な関数 \(+k\) の例外）を表現せざるを得なくなるためです。
In our experiments we find that the first option doesn't happen -all experiments reach 100% training accuracy at some point, and this point is not considerably affected by changing the number of outliers \(k\). The second phenomenon happens in a range of training data percentages and number of outliers \(k\) -increasing \(k\) decreases the range of training data percentages for which the optimization procedure converges to models that generalize. However the effect of introducing a small number of outliers
(up to 1000) is not very pronounced -see Figure 6. We interpret this as additional evidence that the capacity of the network and optimization procedure is well beyond the capacity needed for memorizing all the labels on the training data, and that generalization happening at all requires a
non-trivial explanation.
私たちの実験では、最初の選択肢は発生しないことがわかりました。すべての実験は、ある時点で100%の学習精度に達しますが、この点は外れ値の数 \(k\) を変更しても大きな影響を受けません。2つ目の現象は、学習データの割合と外れ値の数 \(k\) の範囲で発生します。\(k\) が増加すると、最適化手順が一般化するモデルに収束する学習データの割合の範囲が狭まります。しかし、少数の外れ値（最大1000個）を導入した場合の影響はそれほど顕著ではありません（図6を参照）。これは、ネットワークと最適化手順の容量が学習データのすべてのラベルを記憶するのに必要な容量をはるかに超えていること、そして一般化が起こるには何らかの説明が必要であることを示すさらなる証拠であると解釈しています。
We believe it is useful to explore how predictive common generalization measures are of generalization on small algorithmic datasets presented in this paper. In a preliminary investigation we found that sharpness Hochreiter & Schmidhuber (1997) of the minimum found by a trained network measure
seems to be predictive of generalization on one of these datasets. We trained multiple networks with different initialization seeds for a fixed number a steps on the \(S_5\) composition objective, until approximately half of them achieved high validation accuracy. We then used the method described in
Keskar et al. (2016) to calculate the sharpness approximation value, \(\phi\). We found that the validation accuracy and the \(φ\) score across our trained networks had Spearman correlation coefficient of -0.79548 (significant with p<0.000014). This is suggestive that grokking may only happen after the network's parameters are in flatter regions of the loss landscape. It would be valuable for future work to explore this hypothesis, as well as test other generalization measures.
本論文で提示した小規模アルゴリズムデータセットにおいて、一般的な一般化指標が一般化をどの程度予測できるかを調査することは有益であると考える。予備調査において、学習済みネットワーク指標によって発見された最小値のHochreiter & Schmidhuber (1997) によるシャープネスは、これらのデータセットの1つにおいて一般化を予測する指標となる可能性が高いことがわかった。我々は、異なる初期化シードを持つ複数のネットワークを、\(S_5\)構成目的関数で固定ステップ数aで学習させ、約半数のネットワークが高い検証精度を達成するまで学習させた。次に、Keskar et al. (2016) で説明されている方法を用いてシャープネス近似値\(\phi\)を計算した。学習済みネットワーク全体の検証精度と\(φ\)スコアのスピアマン相関係数は-0.79548（p<0.000014で有意）であった。これは、ネットワークのパラメータが損失ランドスケープのより平坦な領域に入った後にのみ、グロッキングが発生する可能性があることを示唆している。この仮説を調査し、他の一般化尺度をテストすることは、今後の研究にとって価値があるでしょう。
Figure 7: Networks trained on the \(S_5\) composition objective appear to only grok in relatively flat regions of the loss landscape.
図 7: \(S_5\) 構成目的でトレーニングされたネットワークは、損失ランドスケープの比較的平坦な領域でのみ理解するようです。